#define PRIMELISTSIZE1 1000
#define STEP 1000
#define PRIMELISTSIZE2 1778

int prime_list_32[PRIMELISTSIZE2] = 
{
11863279,
11863259,
11863253,
11863249,
11863237,
11863213,
11863207,
11863183,
11863171,
11863153,
11863151,
11863133,
11863121,
11863109,
11863099,
11863073,
11863067,
11863057,
11863039,
11863037,
11863031,
11863021,
11862989,
11862979,
11862959,
11862919,
11862911,
11862881,
11862869,
11862857,
11862839,
11862803,
11862791,
11862761,
11862713,
11862703,
11862701,
11862679,
11862673,
11862661,
11862623,
11862611,
11862581,
11862577,
11862569,
11862563,
11862547,
11862527,
11862493,
11862469,
11862439,
11862391,
11862373,
11862343,
11862317,
11862313,
11862307,
11862293,
11862271,
11862269,
11862259,
11862241,
11862239,
11862233,
11862229,
11862223,
11862217,
11862203,
11862199,
11862167,
11862157,
11862083,
11862049,
11862031,
11862029,
11862013,
11862007,
11861987,
11861959,
11861953,
11861921,
11861917,
11861887,
11861879,
11861873,
11861849,
11861827,
11861819,
11861803,
11861791,
11861749,
11861713,
11861711,
11861701,
11861693,
11861687,
11861683,
11861671,
11861659,
11861639,
11861627,
11861611,
11861599,
11861581,
11861579,
11861573,
11861569,
11861539,
11861527,
11861467,
11861441,
11861429,
11861413,
11861411,
11861407,
11861401,
11861371,
11861363,
11861357,
11861351,
11861327,
11861303,
11861299,
11861293,
11861273,
11861237,
11861231,
11861221,
11861219,
11861197,
11861191,
11861167,
11861159,
11861141,
11861131,
11861107,
11861099,
11861093,
11861089,
11861081,
11861071,
11861033,
11861011,
11860993,
11860973,
11860963,
11860897,
11860867,
11860859,
11860837,
11860811,
11860789,
11860787,
11860777,
11860753,
11860741,
11860727,
11860703,
11860699,
11860697,
11860691,
11860687,
11860669,
11860661,
11860649,
11860643,
11860637,
11860627,
11860619,
11860613,
11860573,
11860547,
11860517,
11860489,
11860487,
11860483,
11860477,
11860469,
11860411,
11860397,
11860379,
11860327,
11860267,
11860243,
11860231,
11860223,
11860207,
11860171,
11860151,
11860133,
11860109,
11860103,
11860097,
11860087,
11860081,
11860049,
11860039,
11860031,
11860021,
11859997,
11859989,
11859979,
11859961,
11859929,
11859923,
11859917,
11859907,
11859901,
11859893,
11859889,
11859877,
11859853,
11859847,
11859833,
11859821,
11859817,
11859791,
11859751,
11859739,
11859719,
11859713,
11859707,
11859643,
11859611,
11859583,
11859571,
11859569,
11859563,
11859541,
11859539,
11859509,
11859503,
11859487,
11859481,
11859473,
11859461,
11859457,
11859451,
11859433,
11859427,
11859383,
11859377,
11859371,
11859359,
11859349,
11859311,
11859307,
11859293,
11859269,
11859247,
11859241,
11859233,
11859187,
11859179,
11859167,
11859163,
11859157,
11859151,
11859139,
11859137,
11859109,
11859101,
11859083,
11859079,
11859077,
11859073,
11859061,
11859049,
11859031,
11859017,
11858989,
11858971,
11858969,
11858953,
11858947,
11858921,
11858897,
11858893,
11858851,
11858839,
11858813,
11858807,
11858801,
11858783,
11858779,
11858747,
11858729,
11858723,
11858719,
11858701,
11858683,
11858659,
11858657,
11858629,
11858599,
11858597,
11858579,
11858573,
11858569,
11858557,
11858551,
11858543,
11858533,
11858479,
11858447,
11858443,
11858423,
11858387,
11858381,
11858377,
11858359,
11858323,
11858311,
11858291,
11858281,
11858279,
11858269,
11858267,
11858243,
11858227,
11858201,
11858177,
11858159,
11858149,
11858131,
11858101,
11858059,
11858057,
11858051,
11858039,
11858029,
11858023,
11858017,
11857999,
11857991,
11857969,
11857931,
11857913,
11857907,
11857889,
11857883,
11857877,
11857873,
11857837,
11857831,
11857819,
11857817,
11857801,
11857793,
11857787,
11857777,
11857763,
11857759,
11857753,
11857751,
11857711,
11857709,
11857697,
11857693,
11857667,
11857661,
11857613,
11857591,
11857589,
11857543,
11857529,
11857523,
11857519,
11857499,
11857493,
11857481,
11857477,
11857457,
11857453,
11857451,
11857423,
11857409,
11857393,
11857369,
11857367,
11857361,
11857333,
11857331,
11857327,
11857303,
11857291,
11857267,
11857249,
11857243,
11857217,
11857193,
11857151,
11857147,
11857127,
11857123,
11857099,
11857093,
11857091,
11857081,
11857073,
11857067,
11857061,
11857049,
11857039,
11857037,
11857033,
11857003,
11856979,
11856953,
11856947,
11856919,
11856899,
11856883,
11856877,
11856857,
11856841,
11856821,
11856811,
11856763,
11856731,
11856727,
11856709,
11856697,
11856673,
11856659,
11856653,
11856641,
11856629,
11856583,
11856553,
11856547,
11856541,
11856517,
11856511,
11856479,
11856473,
11856469,
11856461,
11856419,
11856409,
11856373,
11856371,
11856359,
11856343,
11856329,
11856311,
11856307,
11856287,
11856281,
11856269,
11856239,
11856223,
11856199,
11856193,
11856179,
11856161,
11856151,
11856139,
11856113,
11856107,
11856101,
11856071,
11856049,
11856023,
11856001,
11855999,
11855993,
11855989,
11855959,
11855933,
11855911,
11855903,
11855881,
11855869,
11855839,
11855827,
11855813,
11855773,
11855759,
11855747,
11855743,
11855737,
11855731,
11855713,
11855699,
11855689,
11855687,
11855653,
11855633,
11855593,
11855581,
11855567,
11855551,
11855549,
11855531,
11855521,
11855507,
11855491,
11855489,
11855413,
11855407,
11855387,
11855383,
11855381,
11855359,
11855357,
11855353,
11855351,
11855339,
11855329,
11855321,
11855309,
11855303,
11855269,
11855267,
11855231,
11855219,
11855213,
11855177,
11855159,
11855149,
11855147,
11855141,
11855111,
11855033,
11855023,
11855017,
11855003,
11854979,
11854961,
11854937,
11854919,
11854901,
11854897,
11854891,
11854883,
11854877,
11854873,
11854853,
11854847,
11854813,
11854793,
11854757,
11854709,
11854691,
11854681,
11854607,
11854603,
11854573,
11854571,
11854567,
11854529,
11854523,
11854519,
11854517,
11854489,
11854477,
11854463,
11854441,
11854439,
11854433,
11854429,
11854411,
11854399,
11854379,
11854363,
11854333,
11854331,
11854327,
11854279,
11854267,
11854261,
11854211,
11854169,
11854163,
11854159,
11854147,
11854061,
11854057,
11854019,
11854009,
11854001,
11853991,
11853979,
11853943,
11853931,
11853899,
11853893,
11853889,
11853883,
11853869,
11853857,
11853847,
11853839,
11853817,
11853791,
11853773,
11853761,
11853757,
11853731,
11853719,
11853689,
11853679,
11853649,
11853629,
11853617,
11853613,
11853601,
11853571,
11853557,
11853529,
11853463,
11853451,
11853449,
11853427,
11853421,
11853419,
11853383,
11853367,
11853329,
11853323,
11853319,
11853241,
11853227,
11853221,
11853217,
11853203,
11853181,
11853161,
11853157,
11853133,
11853031,
11853019,
11853001,
11852989,
11852969,
11852959,
11852957,
11852921,
11852917,
11852891,
11852879,
11852873,
11852857,
11852837,
11852833,
11852831,
11852809,
11852807,
11852803,
11852773,
11852767,
11852759,
11852741,
11852719,
11852717,
11852663,
11852657,
11852647,
11852641,
11852623,
11852611,
11852609,
11852591,
11852579,
11852573,
11852557,
11852539,
11852537,
11852531,
11852513,
11852473,
11852459,
11852437,
11852369,
11852359,
11852341,
11852339,
11852327,
11852311,
11852303,
11852297,
11852293,
11852287,
11852279,
11852273,
11852263,
11852251,
11852237,
11852221,
11852209,
11852177,
11852171,
11852161,
11852147,
11852129,
11852089,
11852083,
11852059,
11852053,
11852051,
11852017,
11851997,
11851967,
11851949,
11851933,
11851927,
11851919,
11851909,
11851891,
11851867,
11851859,
11851841,
11851813,
11851799,
11851793,
11851787,
11851759,
11851753,
11851681,
11851673,
11851639,
11851621,
11851613,
11851603,
11851597,
11851591,
11851589,
11851577,
11851559,
11851549,
11851547,
11851529,
11851523,
11851519,
11851493,
11851481,
11851451,
11851447,
11851409,
11851403,
11851373,
11851361,
11851351,
11851349,
11851313,
11851303,
11851291,
11851219,
11851201,
11851181,
11851157,
11851139,
11851127,
11851123,
11851109,
11851093,
11851067,
11851051,
11851033,
11850997,
11850991,
11850983,
11850961,
11850953,
11850947,
11850941,
11850931,
11850919,
11850913,
11850907,
11850899,
11850877,
11850859,
11850829,
11850803,
11850791,
11850749,
11850739,
11850731,
11850701,
11850677,
11850667,
11850611,
11850607,
11850557,
11850541,
11850529,
11850511,
11850481,
11850469,
11850427,
11850407,
11850379,
11850373,
11850367,
11850347,
11850341,
11850283,
11850269,
11850259,
11850247,
11850233,
11850191,
11850169,
11850161,
11850133,
11850127,
11850121,
11850109,
11850103,
11850077,
11850073,
11850061,
11850049,
11850031,
11850023,
11850019,
11850011,
11850001,
11849987,
11849947,
11849933,
11849923,
11849909,
11849891,
11849881,
11849869,
11849813,
11849801,
11849791,
11849771,
11849767,
11849759,
11849743,
11849741,
11849723,
11849713,
11849707,
11849701,
11849699,
11849693,
11849689,
11849683,
11849671,
11849659,
11849653,
11849641,
11849633,
11849599,
11849587,
11849573,
11849569,
11849567,
11849557,
11849507,
11849503,
11849491,
11849473,
11849443,
11849437,
11849417,
11849413,
11849401,
11849399,
11849363,
11849359,
11849339,
11849309,
11849297,
11849291,
11849273,
11849269,
11849251,
11849249,
11849239,
11849237,
11849231,
11849203,
11849183,
11849177,
11849137,
11849129,
11849111,
11849107,
11849093,
11849087,
11849077,
11849069,
11849059,
11849053,
11849039,
11849021,
11848961,
11848937,
11848931,
11848919,
11848909,
11848873,
11848867,
11848861,
11848853,
11848829,
11848801,
11848787,
11848757,
11848751,
11848741,
11848729,
11848721,
11848717,
11848709,
11848691,
11848679,
11848673,
11848663,
11848637,
11848619,
11848601,
11848591,
11848589,
11848553,
11848537,
11848531,
11848523,
11848513,
11848493,
11848489,
11848477,
11848469,
11848451,
11848433,
11848393,
11848379,
11848373,
11848363,
11848351,
11848339,
11848313,
11848297,
11848271,
11848253,
11848247,
11848241,
11848237,
11848219,
11848181,
11848159,
11848157,
11848147,
11848129,
11848117,
11848093,
11848069,
11848043,
11848027,
11848021,
11847977,
11847961,
11847949,
11847907,
11847883,
11847877,
11847853,
11847799,
11847791,
11847761,
11847749,
11847721,
11847701,
11847653,
11847643,
11847637,
11847629,
11847607,
11847593,
11847587,
11847581,
11847571,
11847569,
11847533,
11847529,
11847527,
11847523,
11847499,
11847497,
11847467,
11847463,
11847427,
11847397,
11847391,
11847373,
11847347,
11847343,
11847299,
11847281,
11847271,
11847263,
11847257,
11847233,
11830253,
11814059,
11797861,
11781907,
11765609,
11749061,
11732887,
11716381,
11699993,
11684149,
11667269,
11651309,
11634739,
11618281,
11602949,
11586493,
11570407,
11554009,
11538067,
11522363,
11505511,
11489431,
11472817,
11457029,
11441081,
11424467,
11408317,
11392207,
11375563,
11359163,
11343187,
11326423,
11310521,
11293801,
11278019,
11261317,
11245081,
11228929,
11212433,
11196127,
11179907,
11163877,
11148019,
11131741,
11114879,
11098937,
11082817,
11066729,
11050939,
11034811,
11018591,
11001821,
10985479,
10969193,
10953181,
10937063,
10921171,
10904617,
10888811,
10872223,
10856141,
10840157,
10824139,
10807817,
10791629,
10775437,
10758619,
10742231,
10726003,
10709957,
10693897,
10677893,
10662257,
10646191,
10629929,
10613903,
10597597,
10581289,
10565047,
10549031,
10533073,
10516343,
10500547,
10484483,
10468361,
10452551,
10436291,
10420139,
10403951,
10388171,
10371899,
10356113,
10339639,
10323751,
10307537,
10291129,
10274821,
10259153,
10243201,
10226893,
10210831,
10194593,
10178017,
10161439,
10145197,
10129397,
10113241,
10097149,
10080997,
10064671,
10048859,
10033087,
10017113,
10000987,
9984587,
9968117,
9951703,
9935437,
9919439,
9903083,
9887179,
9870853,
9854791,
9838123,
9821809,
9805793,
9790177,
9774007,
9757703,
9741377,
9725707,
9709379,
9693031,
9677027,
9661009,
9645131,
9628939,
9613127,
9596597,
9581053,
9565291,
9548909,
9533023,
9516809,
9500993,
9484931,
9468793,
9452269,
9436439,
9419909,
9403967,
9387671,
9371371,
9355471,
9339569,
9323669,
9307513,
9291539,
9275377,
9259109,
9243281,
9227321,
9211759,
9195671,
9179591,
9163981,
9147521,
9131957,
9115709,
9099589,
9083521,
9067631,
9051563,
9035357,
9019259,
9002717,
8986751,
8970821,
8954321,
8938301,
8922611,
8907077,
8890823,
8874659,
8858677,
8842541,
8826221,
8810147,
8794081,
8778299,
8762357,
8746637,
8730467,
8714551,
8698813,
8683159,
8666773,
8651117,
8635049,
8618861,
8603183,
8587127,
8571509,
8555317,
8539747,
8523787,
8508217,
8492329,
8476723,
8460533,
8444671,
8428289,
8412169,
8396111,
8380237,
8364329,
8348107,
8332547,
8316449,
8300603,
8284447,
8268907,
8252551,
8236729,
8220881,
8205163,
8189123,
8173427,
8157343,
8141753,
8125373,
8109887,
8093707,
8077463,
8061421,
8045669,
8029717,
8013701,
7997623,
7981837,
7965871,
7949731,
7934089,
7918123,
7902269,
7886297,
7870657,
7854667,
7839269,
7823279,
7807549,
7791857,
7775479,
7759813,
7743737,
7727477,
7711741,
7695707,
7680181,
7664311,
7648439,
7632511,
7616881,
7601081,
7585639,
7569469,
7553437,
7537903,
7521949,
7505863,
7489847,
7474381,
7457993,
7442333,
7426421,
7410857,
7394873,
7378687,
7363123,
7347521,
7331309,
7315673,
7299493,
7283833,
7268039,
7252381,
7236821,
7220921,
7204891,
7189333,
7173233,
7157429,
7141759,
7125413,
7109423,
7094023,
7078283,
7062529,
7046581,
7031281,
7015973,
6999823,
6984193,
6968123,
6952441,
6937027,
6921281,
6905713,
6889789,
6874223,
6858913,
6843289,
6827543,
6811877,
6796591,
6780271,
6764353,
6748897,
6733171,
6717493,
6702197,
6686663,
6670709,
6654877,
6639049,
6622999,
6607379,
6591811,
6576307,
6560669,
6545171,
6529403,
6513613,
6498169,
6482407,
6466487,
6451087,
6435179,
6419299,
6403739,
6388061,
6371879,
6355963,
6340043,
6324401,
6308737,
6293681,
6278309,
6262721,
6247243,
6231497,
6215617,
6199847,
6184289,
6168353,
6152869,
6137477,
6121681,
6105949,
6090569,
6074779,
6058963,
6043417,
6027277,
6011899,
5996687,
5981071,
5965021,
5949313,
5933713,
5918293,
5903251,
5887631,
5872549,
5856709,
5841373,
5825711,
5809861,
5794457,
5778673,
5762759,
5747227,
5731463,
5716021,
5700451,
5685413,
5669803,
5654083,
5638103,
5622731,
5607149,
5591459,
5575601,
5560327,
5544613,
5529079,
5513267,
5497711,
5481989,
5466217,
5450773,
5435533,
5420083,
5404433,
5388689,
5373607,
5357903,
5342327,
5327041,
5311511,
5295839,
5280367,
5264821,
5249411,
5234237,
5218721,
5203477,
5188123,
5172227,
5156839,
5141117,
5125871,
5110561,
5094841,
5079493,
5064119,
5048741,
5033053,
5017637,
5001923,
4986439,
4971409,
4956151,
4940843,
4925419,
4909859,
4894753,
4879937,
4864511,
4849081,
4833989,
4818287,
4803031,
4787569,
4771999,
4756649,
4740979,
4725673,
4710373,
4695079,
4679813,
4664641,
4649119,
4633693,
4618307,
4603031,
4587589,
4572383,
4556933,
4541819,
4526363,
4510687,
4495079,
4480183,
4464877,
4449617,
4434811,
4419773,
4404679,
4389223,
4373647,
4358659,
4342991,
4327621,
4312381,
4297201,
4281481,
4265903,
4250777,
4235411,
4220207,
4204903,
4189583,
4174601,
4159471,
4144267,
4128763,
4113127,
4097957,
4082909,
4067741,
4052383,
4037521,
4022587,
4007447,
3992159,
3976481,
3961229,
3945919,
3930611,
3915761,
3900509,
3885691,
3870299,
3854969,
3839923,
3824591,
3809959,
3794941,
3779443,
3764311,
3748879,
3733397,
3718837,
3703643,
3688757,
3673793,
3658769,
3643331,
3628057,
3613201,
3598691,
3583757,
3568259,
3553453,
3538027,
3522763,
3507587,
3492287,
3476783,
3461291,
3445801,
3431353,
3416267,
3401509,
3386563,
3371419,
3356389,
3341101,
3325991,
3311051,
3295883,
3280759,
3265861,
3250837,
3235819,
3220967,
3206311,
3191603,
3176821,
3162059,
3147101,
3131761,
3117031,
3102371,
3087239,
3072533,
3057647,
3042493,
3027347,
3012137,
2997509,
2982583,
2967647,
2952629,
2937611,
2922677,
2907871,
2892973,
2877899,
2862917,
2847893,
2833211,
2818451,
2804027,
2789327,
2774309,
2759621,
2744551,
2729563,
2714629,
2699903,
2685323,
2670533,
2655571,
2641063,
2626307,
2611597,
2596501,
2581697,
2567447,
2552657,
2537779,
2523163,
2508281,
2493767,
2478937,
2464009,
2449417,
2434681,
2419793,
2405069,
2390207,
2375921,
2361167,
2346473,
2331689,
2316593,
2301709,
2287249,
2272241,
2258083,
2243551,
2228797,
2214161,
2199623,
2184779,
2170153,
2155603,
2141149,
2126623,
2111933,
2097539,
2082917,
2068201,
2053789,
2038969,
2024417,
2010017,
1995977,
1981523,
1966619,
1952023,
1937657,
1923253,
1908923,
1894127,
1879949,
1865509,
1851503,
1836943,
1822703,
1808071,
1793927,
1779497,
1765187,
1750423,
1736281,
1721659,
1707253,
1692967,
1678429,
1664501,
1650059,
1635317,
1621421,
1606897,
1592881,
1578217,
1563967,
1549577,
1535459,
1520707,
1506497,
1492499,
1478467,
1464173,
1450139,
1435919,
1422163,
1407569,
1393663,
1379321,
1365281,
1351199,
1336997,
1322693,
1308719,
1294483,
1280453,
1266281,
1252469,
1238551,
1224193,
1210369,
1195771,
1181963,
1168231,
1154633,
1140563,
1126693,
1112483,
1099051,
1085023,
1071229,
1057279,
1043201,
1029179,
1015451,
1001821,
988061,
973901,
960293,
946133,
932357,
918677,
905071,
891239,
877469,
864013,
850247,
836477,
822883,
809423,
795737,
782191,
768671,
755309,
741509,
728003,
714563,
701341,
687679,
674363,
660893,
647557,
634031,
620363,
607127,
593899,
580733,
567659,
554167,
540863,
527441,
514561,
501217,
488347,
475283,
462493,
449161,
435889,
423257,
410341,
397223,
384407,
371573,
358471,
345769,
333019,
320317,
307873,
295291,
282427,
269947,
257501,
245083,
232523,
220327,
208049,
195787,
183683,
171673,
159499,
147551,
135649,
123853,
112223,
100547,
89203,
77719,
66587,
55589,
44633,
34019,
23741,
13877,
4733
};
